package buaa.leetcode.String;

public class LongestPalindrome {
		public static void main(String[] args ){
			//System.out.println(longestPalindrome1("character"));
			System.out.println(longestPalindrome2("character"));
		}
	    public static String longestPalindrome1(String s) {
	        //dynamic programing 
	        if(s.length() <= 1){
	            return s;
	        }
	        //initiate
	        int maxLen = 0;
	        String maxString = null;
	        int[][] table = new int[s.length()][s.length()];
	        for(int i = 0;i < s.length(); i++){
	            table[i][i] = 1;
	        }
	        for(int i = 0;i < s.length() - 1; i++){
	            if(s.charAt(i) == s.charAt(i+1)){
	                table[i][i+1] = 1;
	            }
	        }
	        for(int l = 3;l <= s.length();l++){
	            for(int i = 0; i <= s.length() - l;i++){
	                int j = i + l -1;
	                if(s.charAt(i) == s.charAt(j)){
	                    table[i][j] = table[i+1][j-1];
	                    if(table[i+1][j-1] > 0){
	                        maxLen = l;
	                        maxString = s.substring(i,j+1);
	                    }
	                }else{
	                    table[i][j] = 0;
	                }
	            }
	        }
	        return maxString;
	    }
	    public static String longestPalindrome2(String s) {
 	       
	        if(s.length() <=1)  
	            return s;  
	       
	        int maxLen = 0;  
	        String longestStr = null;  
	        String tmp = null;
	        int length = s.length(); 
	        for (int i = 0; i < length; i++) {  
	           tmp = helper(s,i,i);
	           if(tmp.length() > maxLen){
	               maxLen = tmp.length();
	               longestStr = tmp;
	           }
	           tmp = helper(s,i,i+1);
	           if(tmp.length() > maxLen){
	               maxLen = tmp.length();
	               longestStr = tmp;
	           }
	        }  
	        return longestStr;  
    }
    public static String helper(String s, int begin, int end){
        while(begin >= 0 && end < s.length() && s.charAt(begin) == s.charAt(end)){
            begin--;
            end++;
        }
        String tmp = s.substring(begin+1,end);
        return tmp;
    } 

}
